perm filename A10.TEX[154,RWF] blob
sn#807829 filedate 1985-09-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \magnification\magstephalf
C00005 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a10.tex[154,phy] \today\hfill}
\bigskip
\noindent{\bf Theorem.}
There are inherently ambiguous context-free languages.
\medskip\noindent
{\bf Proof.} Such a language is
$$L=\{a↑ib↑ic↑j\}+\{a↑ib↑jc↑j\}\,.$$
Let $G$ be any CFG for $L$, and $n$ the corresponding number for $G$
in Ogden's lemma (but at least~3). Let $z=a↑nb↑nc↑{n+n!}$.
Mark all the~$b$s for Ogden's Lemma. Then the only way to pump is for
$z=uvwxy$, where $v=a↑k$, $x=b↑k$, $k≤n$. Since $k$ divides~$n!$,
by pumping $n!/k$ times, we get a derivation of
$a↑{n+n!}b↑{n+n!}c↑{n+n!}$, where there is a phrase including
at least $n!$~each of~$a$'s and~$b$'s, and no~$c$'s.
Now do the same to pump $z=a↑{n+n!}b↑nc↑n$, getting a derivation of
$a↑{n+n!}b↑{n+n!}c↑{n+n!}$ with a phrase including at least $n!$~each
of $b$'s and~$c$'s, and no~$a$'s.
The two phrases overlap (because $n≥3$), but neither is a substring
of the other. They must therefore belong to distinct derivations,
$a↑{n+n!}b↑{n+n!}c↑{n+n!}$ is ambiguous, every grammar for~$L$
is ambiguous, $L$~is inherently ambiguous, and $L$~is not a~DCFL.
Ogden's Lemma is so called because it was originaly used as a lemma
to prove this theorem.
\bigskip
\noindent References: Gross 1964, Ginsburg and Ullman 1966, a \&\ b.
\vfill\eject\end